#include<iostream>
#include<vector>
using namespace std;

// 集装箱数量、轮船的载重量
int	n=5, t=10;

// 各集装箱重量, 不用下标0的元素
int w[] = {5, 2, 6, 4, 3};

// 存放最优解向量
vector<int> bestx;

// 存放最优解的总重量，初始化为0
int bestw = 0;

// 递归算法
void dfs(int cw, int rw, vector<int>&x, int i)
{
	// 找到一个叶子结点
	if (i>=n)
	{
		// 找到一个满足条件的更优解
		if (cw > bestw)
		{
			// 保存更优解
			bestw = cw;
			bestx = x;
		}
	}
	
	// 尚未找完所有集装箱
	else
	{
		// 求剩余集装箱的重量和
		rw-=w[i];
		
		// 左孩子结点剪支：选择满足条件的集装箱
		if (cw+w[i] <= t)
		{
			// 选取集装箱i 
			x[i] = 1;
			
			// 累计当前所选集装箱的重量和 
			cw += w[i];
			dfs(cw, rw, x, i+1);
			
			// 恢复当前所选集装箱的重量和(回溯)
			cw -= w[i];
		}
		
		// 右孩子结点剪支
		if (cw+rw > bestw)
		{
			// 不选择集装箱i
			x[i] = 0;
			dfs(cw, rw, x, i+1);
		}
		
		// 恢复剩余集装箱的重量和(回溯)
		rw+=w[i];
	}
}

// 输出最优解
void disp()
{
	for (int i=0;i<n;i++)
		if (bestx[i]==1)
			printf("  选取第%d个集装箱\n",i);
	printf("  总重量=%d\n",bestw);
}

// 求解简单装载问题
void loading()
{
	// 存储最优解
	bestx.resize(n);
	
	// 解向量
	vector<int> x(n);
	
	// 集装箱的总重量
	int rw = 0;
	for (int i=0; i<n; i++)
		rw += w[i];
	
	// 求解
	dfs(0, rw, x, 0);
}

int main()
{
	printf("最优方案\n");
	
	// 求解简单装载问题
	loading();
	
	// 输出最优解
	disp();
	return 0;
}
